/*
希尔排序（Shell Sort）是一种基于插入排序的排序算法，也称为“缩小增量排序”（Diminishing Increment Sort）算法。
它是一种不稳定排序算法，目前没有最优时间复杂度的证明，一般认为它的时间复杂度在 $O(n\log n)$ 和 $O(n^2)$ 之间。
希尔排序的基本思想是：将待排序的数组按照一定的步长（increment）进行分组，对每个分组使用插入排序算法进行排序，然后逐步减小分组的步长，重复上述操作，直到每个分组的步长为 1，
即对整个数组进行插入排序。希尔排序的效率依赖于步长序列的选取，常用的步长序列是 Hibbard、Sedgewick 等。
https://blog.csdn.net/wang20010104/article/details/124880586
 */

function shellSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let len = arr.length;
    // 步长的选取
    let gap = Math.floor(len / 2);
    // 步长还没缩减完
    while (gap > 0) {
        // 插入排序
        for (let i = gap; i < len; i++) {
            // 每次取出一个元素temp将它插入到已排序的部分中的正确位置 即在已排序的部分从后往前遍历，如果当前元素大于temp，则将当前元素右移一位，直到找到temp的正确位置
            let temp = arr[i];
            // j指向本gap下与其对应的元素首索引
            let j = i - gap;
            // 比较大小(j>=0代表每次都是后面的元素往前插)，这一步找到最终的位置
            while (j >= 0 && arr[j] > temp) {
                // 交换
                arr[j + gap] = arr[j];
                // j移动
                j -= gap;
            }
            // 正确的插入位置应该是j + gap
            arr[j + gap] = temp;
        }
        // 步长缩减
        gap = Math.floor(gap / 2);
    }
    return arr;
}
const arr = [5,2,1,4,5,7,12,3]
console.log(shellSort(arr))
